package lk;

public class D230914 {
    // 字符串的最大公因子

    // 1. 枚举
    // 先找到可以 整除 两个字符串的 长度
    // 然后根据这个长度去获取一个子串
    // 去判断这个子串能否组成 这拼接成 str1 和 str2
    public String gcdOfStrings(String str1, String str2) {
        int len1 = str1.length(), len2 = str2.length();
        for (int i = Math.min(len1, len2); i >= 1; --i) { // 从长度大的开始枚举
            if (len1 % i == 0 && len2 % i == 0) {
                String X = str1.substring(0, i);
                if (check(X, str1) && check(X, str2)) {
                    return X;
                }
            }
        }
        return "";
    }

    public boolean check(String t, String s) {
        int lenx = s.length() / t.length();
        StringBuffer ans = new StringBuffer();
        for (int i = 1; i <= lenx; ++i) {
            ans.append(t);
        }
        return ans.toString().equals(s);
    }



    // 2. 优化枚举
    // 如果存在一个符合要求的字符串 x, 那么它的长度为 str1 和 str2 长度的最大公约数
    class Solution {
        public String gcdOfStrings(String str1, String str2) {
            int len1 = str1.length(), len2 = str2.length();
            String T = str1.substring(0, gcd(len1, len2));
            if (check(T, str1) && check(T, str2)) {
                return T;
            }
            return "";
        }

        public boolean check(String t, String s) {
            int lenx = s.length() / t.length();
            StringBuffer ans = new StringBuffer();
            for (int i = 1; i <= lenx; ++i) {
                ans.append(t);
            }
            return ans.toString().equals(s);
        }

        public int gcd(int a, int b) {
            int remainder = a % b;
            while (remainder != 0) {
                a = b;
                b = remainder;
                remainder = a % b;
            }
            return b;
        }
    }
}
